package 力扣._00周赛._427周赛.问题3;

class Solution {
    public long maxSubarraySum(int[] nums, int k) {
        long sum = 0;
        long max = Long.MIN_VALUE;
        // 滑动窗口 ， 窗口大小为k，2k,3k,4k...
        // 前缀和
        long[] preSum = new long[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        int window = nums.length - (nums.length % k);
        while (window >= 0) {
            // 使用前缀和计算窗口内的和
            long t = max;
            for (int i = window-1; i < nums.length; i++) {
                sum = preSum[i + 1] - preSum[i + 1 - window];
                max = Math.max(max, sum);
            }
            window -= k;
            if(t == max){
                break;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,-11,8};
        int k = 1;
        Solution solution = new Solution();
        System.out.println(solution.maxSubarraySum(nums, k));
    }
}